import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Demo3 {
    public static void main(String[] args) {
        Thread t = new Thread(() -> {

        });
    }

    List<List<String>> ret = new ArrayList<>();
    char[][] arr;
    boolean[] col, dig1, dig2;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        arr = new char[n][n];
        col = new boolean[n];
        dig1 = new boolean[2 * n - 1];
        dig2 = new boolean[2 * n - 1];
        //初始化数组
        for(int i = 0; i < n; i++) {
            Arrays.fill(arr[i], '.');
        }
        dfs(n, 0);
        return ret;
    }
    void dfs(int n, int pos) {
        if(pos == n) {
            List<String> list = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                list.add(new String(arr[i]));
            }
            ret.add(list);
            return;
        }

        for(int i = 0; i < n; i++) {
            if(!col[i] && !dig1[pos + i] && !dig2[pos - i + n - 1]) {
                col[i] = dig1[pos + i] = dig2[pos - i + n - 1] = true;
                arr[pos][i] = 'Q';
                dfs(n, pos + 1);
                col[i] = dig1[pos + i] = dig2[pos - i + n - 1] = false;
                arr[pos][i] = '.';
            }
        }
    }

    int[] col1 = new int[9];//使用位图思想
    int[] row = new int[9];
    int[][] martix = new int[3][3];
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    if((row[i] & (1 << num)) == 0 && (col1[j] & (1 << num)) == 0 &&
                            (martix[i / 3][j / 3] & (1 << num))== 0) {
                        row[i] |= (1 << num);
                        col1[j] |= (1 << num);
                        martix[i / 3][j / 3] |= (1 << num);
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
